Leetcode #206. Reverse Linked List

簡單來說這一題要做反轉鏈結
ex.
input: 1->2->3->4
output: 4->3->2->1

如果你沒做過這題，強烈建議你先思考一下怎麼解。

防雷
防雷
防雷

最直覺的方式可以新建一個slice([]*ListNode)，去把全部的節點都放進去，最後slice從尾去讀取，重新建一個鏈結就行了。

這樣做的時間複雜度為O(n)，空間複雜性O(n)要用slice存下鏈結的地址。

現在為大家介紹一個更好的解法，可以省下一些記憶體。

先來看一下它的流程:

1 2 3 4
2 1 3 4
3 2 1 4
4 3 2 1

每一次新節點都把第一個節點接在後面，當你跑完本個鏈結，就完成反轉了。

來看一下程式:

func reverseLinkedList(head *ListNode) *ListNode {
	// prevNode一開始為是空
	// 這樣第一個節點的next會接到nil，才不會造成無限的鏈結
	var prevNode *ListNode
	currentNode := head

	// 節點交換的過程
	for currentNode != nil {
		temp := currentNode.Next
		currentNode.Next = prevNode // 最前面的節點接到目前節點的後面
		prevNode = currentNode
		currentNode = temp
	}

	return prevNode // 回傳第一個節點
}

明天來解其他題目～